1. Field of the Invention
This invention relates to digital multipliers and, more specifically, to an architecture for reducing the number of partial products to be added during a multiplication procedure.
2. Brief Description of the Prior Art
Multiplier designs have typically occupied significant chip area and often become an obstacle in meeting speed performance goals. In computing A * B=Y, a number of partial products are generated, this number of partial products being determined by the number of digits in the multiplier B. The partial products are then added to provide the result. There are basically two ways to speed up this multiply operation, these being to reduce the number of partial products to be added and/or to speed up the accumulation of partial product terms. The reduction in partial products is a difficult problem and generally translates into added hardware complexity and significant layout obstacles, primarily in the routing of signals. For the above stated reasons, designers have traditionally concentrated on increasing the speed of accumulation of partial products to meet multiplication speed performance goals.
When reduction in the number of partial products is of concern, Booth's algorithm as set forth in "A Signed Binary Multiplication Technique" by A. D. Booth, Quart. J. Mech. Math., Vol. 4, part 2, 1951 is probably the most prevalent recoding scheme presently used in the design of multipliers. Its main thrust is in the reduction of partial products by skipping over consecutive "ones" in the multiplier term. This string recoding method looks at overlapping sets of bits in the multiplier term and recodes them to a multiple of the multiplicand term. The number of partial products required can be reduced by a factor of k where r=2 * k is the number radix as noted in Computer Arithmetic Principles, Architecture and Design, by Kai Hwang, Wiley and Sons, 1979. Though other recode schemes of the multiplier term are known in addition to Booth's algorithm and can be utilized herein, the focus herein will be limited to the Booth algorithm.
The Booth method for radix-2 looks at two bits (one bit plus one overlap bit) and selects the appropriate multiple of the multiplicand. The radix-2 recode method is shown in Table 1. Radix-2 does not actually reduce the number of partial products since one bit of the multiplier term is being encoded.
TABLE 1 ______________________________________ Radix-2 Booth Recode bi bi - 1 Output ______________________________________ 0 0 No string (O * multiplicand) 0 1 End of string (1 * multiplicand) 1 0 Start of string (1 * Multiplicand) 1 1 Center of string (0 * multiplicand) ______________________________________
The radix-4 Booth recode method looks at two bits plus one overlap bit. Radix-4 reduces the number of partial products by a factor of 2. Multipliers incorporating the radix-4 Booth recode method are quite common in present day multiplier designs. The radix-4 method is shown in Table 2.
TABLE 2 ______________________________________ Radix-4 Booth Recode bi + 1 bi bi - i Output ______________________________________ 0 0 0 No string (0 * multiplicand) 0 0 1 End of string (1 * multiplicand) 0 1 0 Single 1 (1 * multiplicand) 0 1 1 End of string (2 * multiplicand) 1 0 0 Start of string (-2 * multiplicand) 1 0 1 End/start of string (-1 * multiplicand) 1 1 0 Start of string (-1 * multiplicand) 1 1 1 Center of string (0 * multiplicand) ______________________________________
Radix-8 reduces the number of partial products by a factor of 3. Radix-8 requires an extra adder to generate the 3 times multiplicand term. Additional interconnect also makes the radix-8 multiplier more difficult in layout. However, radix-8 multipliers have become quite popular in recent years due to the reduction factor. The radix-8 method is shown in Table 3.
TABLE 3 ______________________________________ Radix-8 Booth Recode bi + bi + bi - 2 1 bi i Output ______________________________________ 0 0 0 0 No string (O * multiplicand) 0 0 0 1 End of string (1 * multiplicand) 0 0 1 0 Single 1 (1 * multiplicand) 0 0 1 1 End of string (2 * multiplicand) 0 1 0 0 Start of string (2 * multiplicand) 0 1 0 1 End/start of string (3 * multiplicand) 0 1 1 0 Start of string (3 * multiplicand) 0 1 1 1 Center of string (4 * multiplicand) 1 0 0 0 Start of string (-4 * multiplicand) 1 0 0 1 End/start of string (-3 * multiplicand) 1 0 1 0 Start, Single 1 (-3 * multiplicand) 1 0 1 1 End/start of string (-2 * multiplicand) 1 1 0 0 Start of string (-2 * multiplicand) 1 1 0 1 End/start of string (-1 * multiplicand) 1 1 1 0 Start of string (-1 * multiplicand) 1 1 1 1 Center of string (O * multiplicand) ______________________________________
The tradeoff between hardware complexity and reduction in the number of partial products reaches a major obstacle at radix-16. Extra adders are required to generate the 3, 5, 6 and 7 times the multiplicand term (2, 4 and 8 being simple shifts of 1, 2 and 3 positions respectively). Also, the interconnect becomes increasingly difficult to route. The reduction factor of four is appealing, however the hardware/interconnect cost is high. Despite this problem, there are a few designs that incorporate the radix-16 multiplier, but they are rare.
In the case of higher radix multipliers, extra adders are required to generate the different multiples of the multiplicand term. In the case of radix-16, one through eight times the multiplicand is required with the negative of each multiple to be generated locally at each partial product stage. Two, four and eight are just simple left shifts of the multiplicand while three, five, six and seven each require an adder. The broadcast of each of these multiples through the multiplier array becomes very difficult in layout.